<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Documentation - C API</title>
  <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Documentation - C API
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
<ul>
<li><a href="../mdoc/mdoc.html">Matlab API</a>
</li>
<li><a href="index.html" class='active' >C API</a>
</li>
<li><a href="../man/man.html">Man pages</a>
</li>
</ul></li>
<li><a href="../overview/tut.html">Tutorials</a>
</li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
    
    <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>
    <div class="doxygen">
<div>
<!-- Generated by Doxygen 1.7.5.1 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">KD-trees and forests </div>  </div>
</div>
<div class="contents">
<div class="textblock"><dl class="author"><dt><b>Author:</b></dt><dd>Andrea Vedaldi</dd></dl>
<p><a class="el" href="kdtree_8h.html">kdtree.h</a> implements a KD-tree object, a data structure that can efficiently index moderately dimensional vector spaces. Both best-bin-first <a class="el" href="citelist.html#CITEREF_beis97shape">[3]</a> and randomized KD-tree forests are implemented <a class="el" href="citelist.html#CITEREF_silpa-anan08optimised">[10]</a> , <a class="el" href="citelist.html#CITEREF_muja09fast">[8]</a> . Applications include fast matching of feature descriptors.</p>
<ul>
<li><a class="el" href="kdtree.html#kdtree-overview">Overview</a></li>
<li><a class="el" href="kdtree.html#kdtree-tech">Technical details</a></li>
</ul>
<h2><a class="anchor" id="kdtree-overview"></a>
Overview</h2>
<p>To create a <a class="el" href="structVlKDForest.html" title="KDForest object.">VlKDForest</a> object use <a class="el" href="kdtree_8h.html#af0e747c0b4e989d2800e17eb2b9fd6ec" title="Create new KDForest object.">vl_kdforest_new</a> specifying the dimensionality of the data and the number of trees in the forest. With one tree only, the algorithm is analogous to <a class="el" href="citelist.html#CITEREF_beis97shape">[3]</a> (best-bin KDTree). Multiple trees correspond to the randomized KDTree forest as in <a class="el" href="citelist.html#CITEREF_silpa-anan08optimised">[10]</a> , <a class="el" href="citelist.html#CITEREF_muja09fast">[8]</a> .</p>
<p>To let the KD-tree index some data use <a class="el" href="kdtree_8h.html#ac886f1fd6024a74e9e4a5d7566b2125f" title="Build KDTree from data.">vl_kdforest_build</a>. Note that for efficiency KD-tree does not copy the data but retains a pointer to it. Therefore the data must exist (and not change) until the KD-tree is deleted. To delete the KD-tree object, use <a class="el" href="kdtree_8h.html#a68bcecfea6e63a41aafbd5ea9ca1a418" title="Delete KDForest object.">vl_kdforest_delete</a>.</p>
<p>To find the N nearest neighbors to a query point use <a class="el" href="kdtree_8h.html#a2af87b58193ea0314fa971f8678e4e8c" title="Query operation.">vl_kdforest_query</a>. To set a maximum number of comparisons per query and calculate approximate nearest neighbors use <a class="el" href="kdtree_8h.html#a4bf926f9406cec740d564b703236c68d" title="Set the maximum number of comparisons for a search.">vl_kdforest_set_max_num_comparisons</a>.</p>
<h2><a class="anchor" id="kdtree-tech"></a>
Technical details</h2>
<p><a class="el" href="structVlKDForest.html" title="KDForest object.">VlKDForest</a> implements the best-bin-first kd-tree of <a class="el" href="citelist.html#CITEREF_beis97shape">[3]</a> .</p>
<p><b>Construction.</b> Given a set of points <img class="formulaInl" alt="$ x_1,\dots,x_n \in \mathbb{R}^d $" src="form_155.png"/>, the algorithm recursively partitions the <em>d</em> dimensional Euclidean space <img class="formulaInl" alt="$ \mathbb{R}^d $" src="form_156.png"/> into (hyper-) rectangles.</p>
<p>Partitions are organized into a binary tree with the root corresponding to the whole space <img class="formulaInl" alt="$ \mathbb{R}^d $" src="form_156.png"/>. The algorithm refines each partition by dividing it into two halves by thresholding along a given dimension. Both the splitting dimension and the threshold are determined as a statistic of the data points contained in the partition. The splitting dimension is the one which has largest sample variance and the splitting threshold is either the sample mean or the median. Leaves are atomic partitions and they contain a list of zero or more data points (typically one).</p>
<p><b>Querying.</b> Querying amounts to finding the N data points closer to a given query point <img class="formulaInl" alt="$ x_q \in \mathbb{R}^d $" src="form_157.png"/>. This is done by branch-and-bound. A search state is an active partition (initially the root) and it is weighed by the lower bound on the distance of any point in the partition and the query point. Such a lower bound is trivial to compute because partitions are hyper-rectangles. </p>
</div></div>
     <!-- Doc Here -->
    </div>
   
   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 
